200. Number of Islands 【DFS】

題目：
給一個由 '1'（陸地） 和 '0'（水） 組成的二維網格 grid
計算裡面有幾個「島嶼（islands）」
一座「島」是由水平或垂直相連的 '1' 組成
四個方向相連才算同一座島，斜角連接的不算

範例：

• Example 1:
  Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
  ]
  Output: 1

• Example 2:
  Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
  ]
  Output: 3

想法：
一直往深處走到底，再回頭繼續找下一條路

程式碼：

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

        // 掃描每一個格子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;            // 發現新島
                    dfsMark(grid, i, j, m, n); // 用DFS把整座島 "淹沒"（標成 '0'）
                }
            }
        }
        return count;
    }

    // DFS：把與 (r,c) 連通的所有 '1' 標成 '0'
    private void dfsMark(char[][] grid, int r, int c, int m, int n) {
        // 邊界與已是水（或已訪問）才返回
        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] == '0') return;

        grid[r][c] = '0'; // 標記為已訪問（改成0）

        // 四個方向遞迴
        dfsMark(grid, r - 1, c, m, n); // up
        dfsMark(grid, r + 1, c, m, n); // down
        dfsMark(grid, r, c - 1, m, n); // left
        dfsMark(grid, r, c + 1, m, n); // right
    }
}

實際操作：

1 1 0 0
1 0 0 0
0 0 1 0

Step1:
外層掃到 (0,0) 是 '1' → 找到新島 → count = 1
→ 呼叫 DFS(0,0)

Step2:
DFS(0,0)：把 (0,0) 改成 '0'（淹掉）

檢查四個方向：

上（-1,0）超界 → 跳過
下（1,0）是 '1' → 再呼叫 DFS(1,0)
左（0,-1）超界 → 跳過
右（0,1）是 '1' → 再呼叫 DFS(0,1)

→ DFS 直到所有相連的 '1' 都變成 '0'

Step3:
當第一座島整個被「走完」後，DFS 返回
繼續掃描地圖，發現 (2,2) 又是 '1' → 新島！ count = 2
→ 再 DFS(2,2)

結果回傳： 2